package com.github.yangyishe.p300;

import java.util.Arrays;

/**
 * 287. 寻找重复数
 * https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked
 * todo 已经做出来，但效率较低
 *
 * 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
 *
 * 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
 *
 * 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,3,4,2,2]
 * 输出：2
 * 示例 2：
 *
 * 输入：nums = [3,1,3,4,2]
 * 输出：3
 * 示例 3 :
 *
 * 输入：nums = [3,3,3,3,3]
 * 输出：3
 *
 *
 *
 *
 * 提示：
 *
 * 1 <= n <= 105
 * nums.length == n + 1
 * 1 <= nums[i] <= n
 * nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
 *
 *
 * 进阶：
 *
 * 如何证明 nums 中至少存在一个重复的数字?
 * 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
 */
public class Problem287 {
    public static void main(String[] args) {
        int[] nums=new int[]{3,1,3,4,2};

        Problem287 problem287 = new Problem287();
        int duplicate = problem287.findDuplicate(nums);
        System.out.println("duplicate = " + duplicate);

//        int[] results = problem287.standardBinBucket(0b100);
//        System.out.println("Arrays.toString(results) = " + Arrays.toString(results));
//        int[] binBucket = problem287.binBucket(nums);
//        System.out.println("Arrays.toString(binBucket) = " + Arrays.toString(binBucket));
    }

    /**
     * 思路：
     * 最暴力的思路，是将所有元素进行排序，之后遍历获取重复元素，如此，则时间复杂度为O(nlogn)
     * 其次一种做法，是设定一个大小为10^5个大小的bitmap,之后遍历每一个数，直到遇到重复值为止（手动滑稽）
     * 或者从i=0开始，对对应位置的数字与索引，进行cas，直到遇到重复索引，但需要修改数组
     *
     * 还有一种思路，参考桶排序。统计每个桶的数量，如果多于实际应该出现的数量，则必然为重复数
     *
     *
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        int[] standardBinBucket = standardBinBucket(nums.length - 1);
        int[] binBucket = binBucket(nums);

        int bv=1;
        int result=0;
        for(int i=0;i<binBucket.length;i++){
            int bcount = binBucket[i];
            int scount = standardBinBucket[i];
            if(bcount>scount){
                result|=bv;
            }
            bv<<=1;
        }


        return result;
    }


    /**
     * 譬如12345。
     * 则万位上：
     *  0出现9999次（1~9999），
     *  1出现2346次（10000~12345）
     *  其余位均为0
     * 千位上：
     *  0出现1999次（1~999，10000~10999），
     *  1出现2000次（1000-1999，11000~11999），
     *  2出现1346次（2000~2999，12000~12345），
     *  3出现1000次（3000~3999），
     *  之后所有数字与3一样，均出现1000次
     * 百位上：
     *  0出现1299次（1~99，1000~1099，2000~2999，……，12000~12099），
     *  1出现1300次（100~199，1100~1199，……，12100~12199），
     *  2出现1300次（200~299，1200~1299，……，12200~12299），
     *  3出现1246次（300~399，1300~1399，……，12300~12345），
     *  4出现1200次（400~499，1400~1499，……，11400~11499），
     *  之后所有数字与4一样，均出现1200次。
     * 十位上：
     *  0出现1239次（1~9，100~109，……，12300~12309），
     *  1出现1240次（10~19，110~119，……，12310~12319），
     *  2，3均出现1240次，
     *  4出现1236次（40~49，140~149，……，12340~12345）
     *  5出现1230次，之后均出现1236次
     * 个位上：
     *  0出现1234次（10，……，12340）
     *  1出现1235次（1，11，……，12341）
     *  2~5出现1235次，
     *  6~9出现1234次
     *
     * 所以便可总结规律，如果一个数n可以表示为10000*a+1000*b+100*c+10*d+e
     *
     *
     *
     *
     *
     * @param n
     * @return
     */
    private int[][] maxBucket(int n){
        int[][] bucket=new int[5][10];
        for(int i=0;i<5;i++){
            int v=n%10;
            for(int j=0;j<v;j++){
                bucket[i][j]=v;
            }
        }
        return bucket;
    }

    /**
     * 优化版：
     * 将原来的十进制数字桶，改为二进制数字桶，计算更加容易。统计1出现的频次即可。
     * 如一个数字22，二进制为10110b。则各位1出现的次数：
     * 右1位：出现1011次，即11次
     * 右2位：出现次数=1010+if(1==1,0+1,0)=11次。
     * 右3位：出现次数=1000+if(1==1,10+1,0)=11次。
     * 右4位，出现次数=1000+if(0==1,110+1,0)=8次。
     * 右5位，出现次数=0+if(1==1,0110+1,0)=7次。
     *
     * 即判定某一位出现1的次数时，将该数分为3部分a,b,c。
     * 其中a是该位左侧部分，b是该位的值，c是该位右侧部分。
     * 出现的次数就等于：fillSuffixZero(a)>>1+if(b==1,c+1,0)
     * @return
     */
    private int[] standardBinBucket(int n){
        int comp=1;
        int mov=0;
        int[] results=new int[18];
        while(comp<=n){
            int left=(n>>(mov+1))<<(mov+1);
            int mid=n&comp;
            int right=n%comp;

            int count=(left>>1)+(mid!=0?right+1:0);
            results[mov]=count;

            comp<<=1;
            mov++;
        }

        return results;
    }

    private int[] binBucket(int[] nums){

        int[] results=new int[18];

        int temp;
        int mov;
        for(int num:nums){
            temp=num;
            mov=0;
            while(temp!=0){
                if((temp&1)!=0){
                    results[mov]++;
                }

                temp>>=1;
                mov++;
            }
        }


        return results;
    }


}
